package com.linchong.dynamicprogramming.medium;

import lombok.extern.slf4j.Slf4j;


/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-17 10:15
 * @Description: CoinChange$dp-322-零钱兑换-https://leetcode-cn.com/problems/coin-change/
 */
@Slf4j
public class CoinChange {
	/**
	 * 【求最大/最小值动态规划】
	 * 有三种硬币，分别面值为2元、5元、7元，每种硬币都有足够多；
	 * 买一本数需要27元
	 * 如何使用最少的硬币组合正好付清，不需要对方找钱。
	 */

	public static void main(String[] args) {
		CoinChange instance = new CoinChange();
		int money = 11;
		// leetcode
		int[] coins = {2,5,7};
		int coinChange = instance.coinChange(coins, money);
		log.info("coin change:[{}]",coinChange);

		int coinChange2 = instance.coinChange2(coins,money);
		log.info("coin change2:[{}]",coinChange2);
		//自定义测试
		test(instance, money);
	}

	private static void test(CoinChange instance, int money) {
		// 采用递归算法，且未优化
		int step = instance.recursionCalculation(money);
		log.info("execute:[{}]times,step:[{}]", counter, step);
		int dpStep = instance.dynamicProgram(money);
		log.info("dynamic programming:[{}]",dpStep);
	}

	/**
	 * 零钱找零
	 *
	 * @param coins 硬币数组
	 * @param money 总金额
	 * @return 最优结果
	 */
	public int coinChange(int[] coins, int money) {
		// int n = coins.length;
		// 金额，0...M
		int[] f = new int[money + 1];
		// 初始条件
		f[0] = 0;
		for (int i = 1; i <= money; i++) {
			f[i] = Integer.MAX_VALUE;
			// 开始选择最后一枚硬币，
			for (int value : coins) {
				// 最后一枚硬币面额小于i，i>value,即如果最后剩余金额5，硬币6不能使用
				// 且最后一枚硬币能够拼出来，i-value默认为Integer.MAX_VALUE
				// 且最后一枚硬币的解是最优解,f[i-value]+1的值小于f[i]值
				if (i >= value && f[i - value] != Integer.MAX_VALUE && f[i - value] + 1 < f[i]) {
					f[i] = f[i - value] + 1;
				}
				// 这样可能会好理解
				//for(int j=0;j<n;j++){
				//  if (i >= value && f[i - value] != Integer.MAX_VALUE && f[i - value] + 1 < f[i]) {
				//		f[i] = f[i - value] + 1;
				//	}
				//}
			}
		}
		if (f[money] == Integer.MAX_VALUE) {
			return -1;
		} else {
			return f[money];
		}
	}

	private static int counter = 0;

	/**
	 * 递归计算
	 *
	 * @param x 金额
	 * @return
	 */
	int recursionCalculation(int x) {
		counter++;
		if (x == 0) {
			return 0;
		}
		int res = Integer.MAX_VALUE-1;

		if (x >= 2) {
			res = Math.min(recursionCalculation(x - 2) + 1, res);
		}

		if (x >= 5) {
			res = Math.min(recursionCalculation(x - 5) + 1, res);
		}

		if (x >= 7) {
			res = Math.min(recursionCalculation(x - 7) + 1, res);
		}
		return res;
	}

	int dynamicProgram(int x) {
		int res = Integer.MAX_VALUE - 1;
		if (x < 0) {
			return res;
		}
		int[] coin = new int[x + 1];
		coin[0] = 0;
		for (int i = 1; i <= x; i++) {
			int coin2, coin5, coin7;
			if (i - 2 < 0) {
				coin2 = Integer.MAX_VALUE - 1;
			} else {
				coin2 = coin[i - 2] + 1;
			}
			if (i - 5 < 0) {
				coin5 = Integer.MAX_VALUE - 1;
			} else {
				coin5 = coin[i - 5] + 1;
			}
			if (i - 7 < 0) {
				coin7 = Integer.MAX_VALUE - 1;
			} else {
				coin7 = coin[i - 7] + 1;
			}
			int temp = Math.min(coin2, coin5);
			coin[i] = Math.min(temp, coin7);
			res = coin[i];
		}
		if(res==Integer.MAX_VALUE-1){
			return -1;
		}else{
			return res;
		}
	}

	/**
	 *
	 * @param coins
	 * @param amount
	 * @return
	 */
	public int coinChange2(int[] coins, int amount) {
		//范围，0<=x<=amount
		int[] res = new int[amount+1];
		res[0]=0;
		// 计算
		for (int i = 1; i <= amount; i++) {
			res[i] = Integer.MAX_VALUE;
			// 计算每种金额下的最后一次硬币组合
			for (int coin : coins) {
				// 当最后剩余金额大于硬币金额时才能被选择
				// 当前选择res[i-coins[j]已经是最大值时，不必选择
				// 当当前所选金额的策略不是最优时，才能被替换，即次数不是最小
				if (i >= coin && res[i - coin] != Integer.MAX_VALUE && res[i - coin] + 1 < res[i]) {
					res[i] = res[i - coin] + 1;
				}
			}
		}
		if(res[amount]==Integer.MAX_VALUE){
			return -1;
		}
		return res[amount];
	}
}
